/*
 * @lc app=leetcode.cn id=21 lang=swift
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

class Solution21 {
    // 合并两个有序链表
    // 采用双指针法
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let vHead = ListNode(-1)
        var p1 = l1
        var p2 = l2
        var tail:ListNode? = vHead
        while p1 != nil && p2 != nil {
            if p1!.val < p2!.val {
                tail?.next = p1
                p1 = p1?.next
            } else {
                tail?.next = p2
                p2 = p2?.next
            }
            tail = tail?.next
        }
        while p1 != nil {
            tail?.next = p1
            tail = tail?.next
            p1 = p1?.next
        }
        while p2 != nil {
            tail?.next = p2
            tail = tail?.next
            p2 = p2?.next
        }
        return vHead.next
    }
    // 采用分治法
    // 合并链表：子问题为合并两个很小的链表，这两个小链表最终有解法。
    // 整个的思想，就是我想合并两个链表，当前头比较已经出来，我只需要合并剩下的两个链表，以此类推。
    // 这就是一种分治的思想
    func mergeTwoLists2(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard let tmpl1 = l1 else {
            return l2
        }
        guard let tmpl2 = l2 else {
            return l1
        }
        
        if tmpl1.val <= tmpl2.val {
            tmpl1.next = mergeTwoLists2(tmpl1.next, tmpl2)
            return tmpl1
        }else {
            tmpl2.next = mergeTwoLists2(tmpl1, tmpl2.next)
            return tmpl2
        }
    }
    
    // 合并两个升序的链表
    // 采用递归法进行合并
    func mergeTwoLists3(_ l1: ListNode?, _ l2: ListNode?) ->ListNode? {
        guard let l1 = l1 else {
            return l2
        }
        guard let l2 = l2 else {
            return l1
        }
        var node: ListNode?
        if l1.val < l2.val {
            node = l1
            node?.next = mergeTwoLists3(l1.next, l2)
        } else {
            node = l2
            node?.next = mergeTwoLists3(l1, l2.next)
        }
        return node
    }
    
    class func test()  {
        let link1 = createLink(begin: 1,end: 5)
        let link2 = createLink(begin: 3,end: 9)
        let head:ListNode? =  Solution21().mergeTwoLists3(link1, link2)
        var cur:ListNode? = head
        while cur != nil {
            print(cur?.val ?? "")
            cur = cur?.next
        }
    }
    
    class func createLink(begin:Int,end:Int) -> ListNode? {
        var head:ListNode?
        var tail:ListNode?
        for i in begin...end {
            let node = ListNode(i)
            if head == nil {
                head = node
                tail = head
            }
            tail?.next = node
            node.next = nil
            tail = node
        }
        
        return head
    }
}
// @lc code=end

